package practice_2025_10.practice_10_15;

import java.util.Arrays;
import java.util.Stack;

class Solution {
    /**
     * 验证二叉树的前序序列化
     * @param preorder
     * @return
     */
    public boolean isValidSerialization(String preorder) {
        // 前序遍历顺序：根 - 左 - 右
        // 使用栈辅助验证顺序
        Stack<Integer> stack = new Stack<>();
        String[] strs = preorder.split(",");
        if (strs.length == 1 && strs[0].equals("#")) {
            return true;
        } else if (strs[0].equals("#")) {
            return false;
        } else {
            stack.push(2);
        }
        for(int i = 1; i < strs.length; i++) {
            if (stack.isEmpty()) {
                return false;
            }
            int n = stack.pop();
            if (n > 1) {
                stack.push(1);
            }
            if (!strs[i].equals("#")) {
                stack.push(2);
            }
        }
        // System.out.println(stack.toString() + " " + Arrays.toString(strs));
        return stack.isEmpty();
    }

    /**
     * 删除有序数组中的重复项II
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 2) {
            return 2;
        }
        int slow = 2, fast = 2;
        while(fast < len) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#");
    }
}